package ex2.SearchingAndSorting.cn.edu.besti.cs1723.GK2301;

import week7.LinkedBinarySearchTree;
import week8.LinkedHeap;

import java.util.Iterator;

public class Sorting <T extends Comparable<T>>{
    // 选择排序
    public static <T extends Comparable<? super T>> void selectionSort(T[] data)
    {
        int min;
        T temp;

        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++)
                if (data[scan].compareTo(data[min])<0)
                    min = scan;

            //swap(data, min, index);
            temp = data[min];
            data[min] = data[index];
            data[index] = temp;

        }
    }

    // 插入排序
    public static <T extends Comparable<? super T>> void insertionSort(T[] data)
    {
        for (int index = 1; index < data.length; index++)
        {
            T key = data[index];
            int position = index;

            // 元素向后移动一位
            while (position > 0 && data[position-1].compareTo(key) > 0)
            {
                data[position] = data[position-1];
                position--;
            }

            data[position] = key;
        }
    }

    // 冒泡排序
    public static <T extends Comparable<? super T>> void bubbleSort(T[] data)
    {
        int position, scan;
        T temp;

        for (position =  data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap(data, scan, scan + 1);
            }
        }
    }

    // 快速排序
    public static <T extends Comparable<T>> void quickSort(T[] data)
    {
        quickSort(data, 0, data.length - 1);
    }

    private static <T extends Comparable<T>> void quickSort(T[] data, int min, int max)
    {
        if (min < max)
        {
            // create partitions
            int indexofpartition = partition(data, min, max);

            // sort the left partition (lower values)
            quickSort(data, min, indexofpartition - 1);

            // sort the right partition (higher values)
            quickSort(data, indexofpartition + 1, max);
        }
    }

    private static <T extends Comparable<T>> int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        //使用中间数据值作为分区元素
        partitionelement = data[middle];
        // 暂时把它移开
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // 搜索一个元素，它是>分区元素
            while (left < right && data[left].compareTo(partitionelement) <= 0)
                left++;

            // 搜索一个元素，它是<分区元素
            while (data[right].compareTo(partitionelement) > 0)
                right--;

            // 交换元素
            if (left < right)
                swap(data, left, right);
        }

        // 将分区元素移动到适当的位置
        swap(data, min, right);

        return right;
    }



    public static <T extends Comparable<T>> void mergeSort(T[] data)
    {
        mergeSort(data, 0, data.length - 1);
    }

    private static <T extends Comparable<T>> void mergeSort(T[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid+1, max);
            merge(data, min, mid, max);
        }
    }

    @SuppressWarnings("unchecked")
    private static <T extends Comparable<T>> void merge(T[] data, int first, int mid, int last)
    {
        T[] temp = (T[])(new Comparable[data.length]);

        int first1 = first, last1 = mid;  // 第一个子数组的端点
        int first2 = mid+1, last2 = last;  // 第二个子数组的端点
        int index = first1;  // 下一个索引在temp数组中打开

        //  从每个子数组中将较小的项复制到temp，直到有一个子数组的被耗尽
        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1].compareTo(data[first2]) < 0)
            {
                temp[index] = data[first1];
                first1++;
            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }

        //  从第一个子数组(如果有的话)复制剩余的元素
        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
        }

        //  从第二个子数组(如果有的话)复制剩余的元素
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }

        //  将合并后的数据复制到原始数组中
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }

    // 希尔排序
    public static <T extends Comparable<T>>void shellSort(T[] data)
    {
        for(int gap=data.length/2;gap>0;gap=gap/2)
        {
            for(int i=gap;i<data.length;i++)
            {
                int j = i;
                while(j-gap>=0 && data[j].compareTo(data[j-gap])<0)
                {
                    swap(data,j,j-gap);
                    j-=gap;
                }
            }
        }
    }

    private static <T extends Comparable<? super T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    // 堆排序
    public static <T extends Comparable<T>>void heapSort(T[] data)
    {
        LinkedHeap<T> linkedHeap = new LinkedHeap<>();
        for (int i=0;i<data.length;i++)
            linkedHeap.addElement(data[i]);
        for (int i=0;i<data.length;i++)
            data[i] = linkedHeap.removeMin();
    }

    // 二叉查找树排序
    public static <T extends Comparable<T>>void binarySearchTreeSort(T[] data)
    {
        LinkedBinarySearchTree<T> linkedBinarySearchTree = new LinkedBinarySearchTree<>();
        for (int i=0;i<data.length;i++)
            linkedBinarySearchTree.addElement(data[i]);

        Iterator iterator = linkedBinarySearchTree.iteratorInOrder();
        int index = 0;
        while (iterator.hasNext())
        {
            data[index] = (T) iterator.next();
            index++;
        }
    }
}
